package ru.susu.algebra.ranks;

import java.io.BufferedOutputStream;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Comparator;
import java.util.Date;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;

import ru.susu.algebra.number.MapPrimeNumbersProvider;

/**
 * Пытается построить квадраты на основе композиции меньших квадратов
 *
 * @author akargapolov
 * @since: 25.03.2011
 */
public class FullRecSquaresCompositionsFinder
{
	private static Logger _logger = Logger.getLogger("ranks");

	private static int NUMBER = 200;

	private static Map<Integer, BitSet> _factors = new NumbersBitSetFactorizationProvider().performOperation(NUMBER);
	private static Map<Integer, Integer> _primes = new MapPrimeNumbersProvider().performOperation(NUMBER);
	private static int[][] _dp = new int[NUMBER + 1][NUMBER + 1];
	private static TreeSet<Integer> _numbers = Sets.newTreeSet();

	private static Map<Integer, BigInteger[]> _result = Maps.newHashMap();

	private static Set<Set<Integer>> _primeSquares = Sets.newTreeSet(new SetsComparator());

	private static class SetsComparator implements Comparator<Set<Integer>>
	{
		@Override
		public int compare(Set<Integer> o1, Set<Integer> o2)
		{
			Integer[] array1 = o1.toArray(new Integer[0]);
			Integer[] array2 = o2.toArray(new Integer[0]);

			for (int i = 0; i < array1.length && i < array2.length; i++)
				if (!array1[i].equals(array2[i]))
				{
					return array1[i].compareTo(array2[i]);
				}

			return array1.length - array2.length;
		}

	}

	private static PrintStream _printStream;

	private static int _maxPart, _maxPrime, _maxLength;

	public static void main(String[] args) throws Exception
	{
		BasicConfigurator.configure();

		_printStream = new PrintStream(new BufferedOutputStream(new FileOutputStream("Ranks/FullRecSquaresCompositionsFinder_" + NUMBER + ".txt")));
		PrintStream printStreamMax = new PrintStream(new BufferedOutputStream(new FileOutputStream("Ranks/FullRecSquaresCompositionsFinder_Max_" + NUMBER + ".txt")));

		BigInteger[] all = new BigInteger[2];
		Arrays.fill(all, BigInteger.ZERO);
		for (int n = 1; n <= NUMBER; n++)
		{
			_maxPart = _maxPrime = 0;
			_printStream.println("N = " + n);
			Date startTime = new Date();
			BigInteger[] value = new BigInteger[2];
			Arrays.fill(value, BigInteger.ZERO);
			_result.put(n, value);
			rec(n, 1, 0, 0, new BitSet(_primes.size()));
			Date end = new Date();
			_logger.info(n + " executing time: " + (end.getTime() - startTime.getTime()) + "ms");
			_logger.info(Lists.newArrayList(value));
			_printStream.println("Simple = " + value[0]);
			_printStream.println("Complex = " + value[1]);
			_printStream.println();
			all[0] = all[0].add(value[0]);
			all[1] = all[1].add(value[1]);

			printStreamMax.println("N = " + n + " Max number = " + _maxPart + " Max prime = " + _maxPrime + " Max length = " + _maxLength);
			if (_maxPrime > n / 4 && (n != 9 && n != 10))
				throw new RuntimeException("N = " + n + " 4 * max = " + (4 * _maxPrime));
		}

		_printStream.println("All complex squares: " + all[1]);
		_printStream.println("All simple squares: " + all[0]);
		for (Set<Integer> numbers : _primeSquares)
		{
			_printStream.println(numbers);
		}
		_printStream.close();
		printStreamMax.close();
	}

	private static List<Set<Integer>> getComposition(Set<Integer> numbers)
	{
		if (numbers.equals(Sets.newTreeSet(Arrays.asList(1, 9))))
		{
			System.out.print("");
		}
		List<Set<Integer>> result = Lists.newArrayList();
		Integer[] array = numbers.toArray(new Integer[0]);
		for (int i = 1; i < (1 << array.length); i++)
		{
			Set<Integer> tmp = Sets.newTreeSet();
			for (int j = 0; j < array.length; j++)
				if ((i & (1 << j)) > 0)
				{
					tmp.add(array[j]);
				}

			if (_primeSquares.contains(tmp))
			{
				result.add(tmp);
				Set<Integer> tmp1 = Sets.newTreeSet(numbers);
				tmp1.removeAll(tmp);
				result.addAll(getComposition(tmp1));
				return result;
			}
		}
		return result;
	}

	private static void rec(int n, int k, int sum, int length, BitSet bitset)
	{
		if (n == sum)
		{
			BigInteger[] value = _result.get(n);
			if (bitset.isEmpty())
			{
				/*
				_maxLength = Math.max(_maxLength, _numbers.size());
				_maxPart = Math.max(_maxPart, _numbers.last());
				for (Integer part : _numbers)
				{
					Pair<Integer, Integer>[] factorization = NumberUtilities.factorization(BigInteger.valueOf(part));
					_maxPrime = Math.max(_maxPrime, factorization.length == 0 ? 0 : factorization[factorization.length - 1].getKey());
				}
				List<Set<Integer>> composition = getComposition(_numbers);
				_printStream.print(_numbers.toString());
				if (composition.isEmpty())
				{
					value[0] = value[0].add(BigInteger.ONE);
					_primeSquares.add(Sets.newTreeSet(_numbers));
				}
				else
				{
					value[1] = value[1].add(BigInteger.ONE);
					boolean first = true;
					for (Set<Integer> elem : composition)
					{
						_printStream.print(first ? " = " : " + ");
						_printStream.print(elem.toString());
						first = false;
					}
				}
				_printStream.println();*/
			}

			return;
		}
		if (k > n || sum > n)
			return;

		if (recDP(n - sum - k, k + 2) == 1)
		{
			_numbers.add(k);
			BitSet tmp = (BitSet) bitset.clone();
			tmp.xor(_factors.get(k));
			rec(n, k + 2, sum + k, length + 1, tmp);
			_numbers.remove(k);
		}

		if (recDP(n - sum, k + 2) == 1)
		{
			rec(n, k + 2, sum, length, bitset);
		}
	}

	private static int recDP(int n, int k)
	{
		if (n == 0)
			return 1;
		if (k > n)
			return -1;
		if (_dp[n][k] != 0)
			return _dp[n][k];

		int res = -1;

		if (recDP(n - k, k + 2) == 1 || recDP(n, k + 2) == 1)
			res = 1;

		_dp[n][k] = res;
		return res;
	}
}
